﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.StateSpaces;
using Lists = Algoritmia.DataStructures.Lists;
using Algoritmia.Schemes;
using Algoritmia.Utils;

namespace Algoritmia.Problems.SubsetSum
{
    
    public class SubsetSumStateSpace3 : IForwardStateSpace<Tuple<int,int>,int>
    {
        private List<int> _w;
        private int _W;
        public readonly int N;
        private int[] _tailSum;

        public SubsetSumStateSpace3(IEnumerable<int> w, int W)
        {
            _w = w.ToList();
            _W = W;
            N = _w.Count;
            _tailSum = new int[N + 1];

            for(int i = N-1; i >= 0; i--)
            {
                _tailSum[i] = _tailSum[i + 1] + _w[i];
            }

        }

        public Tuple<int, int> Decide(Tuple<int, int> state, int decision)
        {
            var sum = state.Item1;
            var n = state.Item2;

            return new Tuple<int, int>(sum + decision * _w[n],n+1);
        }

        public IEnumerable<int> Decisions(Tuple<int, int> state)
        {
            var sum = state.Item1;
            var n = state.Item2;

            if ( n < N )
            {
                if ( sum < _W)
                {
                    if ( sum + _w[n] + _tailSum[n+1] >= _W)
                    {
                        yield return 1;
                    }
                    if ( sum + _tailSum[n+1] >= _W)
                    {
                        yield return 0;
                    }
                }
            }
        }

        public IEnumerable<Tuple<int, int>> InitialStates
        {
            get { yield return new Tuple<int, int>(0,0); }
        }

        public bool IsFinal(Tuple<int, int> state)
        {
            var sum = state.Item1;
            return sum == _W;
        }
    }



    public class SubsetSumSolver3
    {
        private readonly BacktrackingEnumerator<Tuple<int,int>, int, Lists.IList<int>> _enumerator;

        public SubsetSumSolver3()
        {
            _enumerator = new BacktrackingEnumerator<Tuple<int,int>, int, Lists.IList<int>>(
                    (space, initial, decisions, final) => decisions.Concat(Enumerable.Range(0,((SubsetSumStateSpace3)space).N-decisions.Count)).ToAlgoritmiaList()
                        );
        }

        public Lists.IList<int> Solve(IEnumerable<int> w, int W)
        {
            var space = new SubsetSumStateSpace3(w, W);
            return _enumerator.First(space);
        }
    }
}
